﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/remove-element

/*
题目描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。
例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]

解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
*/

// 方法2——双指针
/*
思路：
很显然，去除val值后的数组的长度一定小于或等于原来数组的长度，
所以我们就可以直接把去掉val值之后的数组写到原来的数组中，这个过程可以通过两个指针来完成。
我们这里的"双指针"不同于以往的"双指针"
这里的"双指针"不再是，左指针和右指针，而是赋值指针和遍历指针
我们用一个ass来控制赋值，每赋值成功ass就往后走一步，用一个erg指针来遍历数组，
如果erg指向的元素不等于val，则通过left将其存入数组中，若等于val则erg继续向右走
left则不动。
*/

// 有了以上分析，那我们写代码也就水到渠成了
int removeElement2(int* nums, int numsSize, int val) {
	assert(nums);
	int* ass = nums;
	int* erg = nums;
	int n = 0; // 记录数组中val的个数，即数组将要减小的长度
	while (erg < nums + numsSize) {
		if (*erg == val) {
			n++;
			erg++;
		}
		else {
			*ass = *erg;
			ass++;
			erg++;
		}
	}
	return numsSize - n;
}
// 时间复杂度：O(n),其中n为序列的长度。我们只需要用erg遍历数组一次即可。
// 空间复杂度：O(1),我们只需要常数的空间保存若干变量。

// 方法2——双指针优化
/*
思路：
如果要移除的元素正好在开头，例如序列{ 1，2, 3, 4，5},当val为1时，我们需要把每一个元素都
左移一位。但注意题目中说的 "元素的顺序可以改变"。实际上我们可以直接将最后一个元素5移动到
序列的 开头，取代元素1，得到序列{5, 2, 3, 4},同样满足题目要求。这个优化在序列中val元素的数量较少时
非常有效。
我们指针left指向序列的开头，right指针指向序列的结尾
left向右遍历，找到一个val后停下，此时将right指向的元素复制到左指针left的位置，然后右指针向左移动一位
如果复制过来的元素恰好也等于val，可以继续把右指针指向的元素的值复制过来，知道左指针指向的元素不等于val为止。
当左指针和右指针重合的时候，左右指针遍历完数组中的所有的元素。
*/

// 有了以上的分析，那我们写起代码来也就水到渠成了：
int removeElement(int* nums, int numsSize, int val) {
	assert(nums);
	int left = 0, right = numsSize;
	while (left < right) {
		if (nums[left] == val) {
			nums[left] = nums[right - 1];
			right--;
		}
		else {
			left++;
		}
	}
	return left;
}

int main() {
	int arr[] = { 0, 1, 2, 2, 3, 0, 4, 2 };
	int len = sizeof(arr) / sizeof(arr[0]);
	int new_len = removeElement1(arr, len, 2);
	int i = 0;
	for (i = 0; i < new_len; i++) {
		printf("%d ", arr[i]);
	}
	return 0;
}